package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int arr[] = new int[9];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 8000);
        }
        int midarr[] = new int[arr.length];
        sort(arr, 0, arr.length - 1, midarr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int arr[], int left, int right, int midarr[]) {
        // 一个？就不分了，直接合
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, midarr);
            sort(arr, mid + 1, right, midarr);
            merge(arr, left, mid, right, midarr);
        }
    }

    // 取闭区间
    private static void merge(int arr[], int left, int mid, int right, int midarr[]) {
        // 左右两部分各自有序，利用中间数组合并
        // 左右两部分一起移动
        int p = left;
        int l = left;
        int r = mid + 1;
        while(l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                midarr[p++] = arr[l++];
            } else {
                midarr[p++] = arr[r++];
            }
        }
        // 剩余部分补进去
        while (l <= mid) {
            midarr[p++] = arr[l++];
        }
        while (r <= right) {
            midarr[p++] = arr[r++];
        }

        // 移回原位
        for (int k = left; k <= right; k++) {
            arr[k] = midarr[k];
        }
    }
}
